package com.leetcode.专项突破.排序算法全解析;

import com.leetcode.common.utils.ArrayUtils;
import java.util.Arrays;

/**
 * @author 覃国强
 * @date 2022-03-03 16:11
 */
public class A02_选择排序 {

  public static void main(String[] args) {
    int[] arr = ArrayUtils.randomArr(10);
    System.out.println(Arrays.toString(arr));
    selectSort(arr);
    System.out.println(Arrays.toString(arr));
  }

  public static void selectSort(int[] nums) {
    for (int left = 0, right = nums.length - 1; left < right; ++left, --right) {
      int minIndex = left;
      int maxIndex = right;
      for (int i = left; i <= right; ++i) {
        minIndex = nums[i] < nums[minIndex] ? i : minIndex;
        maxIndex = nums[i] > nums[maxIndex] ? i : maxIndex;
      }
      if (nums[minIndex] == nums[maxIndex]) {
        return;
      }
      swap(nums, left, minIndex);
      // 如果最大值在首位，此时，首位已经被替换到 minIndex 位置了，需要更新一下 maxIndex 的值
      if (maxIndex == left) {
        maxIndex = minIndex;
      }
      swap(nums, right, maxIndex);
    }
  }

  public static void swap(int[] nums, int i, int j) {
    if (i == j || nums[i] == nums[j]) {
      return;
    }
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }

}
